package ArbolTrie;

import java.io.Serializable;
import java.util.Iterator;
import Iterador.IteradorSimple;

/**
 * Representa un trie
 * @param <T> Tipo de datos en el trie.
 */

public class Trie < T extends Comparable<? super T> > implements ITrie<T>, Serializable{

    private static final long serialVersionUID = 1L;
	
	// -----------------------------------------------------------------
	// Atributos
	// -----------------------------------------------------------------

	/**
	 * Raiz del trie
	 */
	private NodoTrie<T> raiz;

	/**
	 * Peso del trie
	 */
	private int peso;

	// -----------------------------------------------------------------
	// Constructor
	// -----------------------------------------------------------------

	/**
	 * Construye un trie vacio.<br>
	 * <b> post: </b> Se construyo un trie vacio.
	 */
	public Trie()
	{
		raiz = new NodoTrie<T>( ' ' );
	}

	/**
	 * Construye un trie con la raiz que le llega por parametro. <br>
	 * <b> pre: </b> El caracter de la raiz debe ser ' ' y su elemento==null. <br>
	 * <b> post: </b> Se construyo un trie con la raiz por parametro.
	 * @param nRaiz La raiz del trie
	 * @param nPeso El peso del trie; numero de nodos del trie
	 */
	public Trie( NodoTrie<T> nRaiz, int nPeso )
	{
		raiz = nRaiz;
		peso = nPeso;
	}
	// -----------------------------------------------------------------
	// Metodos
	// -----------------------------------------------------------------

	/**
	 * Inserta un nuevo elemento al trie <br>
	 * <b> pre: </b> nElemento!=null. <br>
	 * <b> post: </b> Se inserto el la palabra con el elemento dado en el trie.
	 * @param nElemento El elemento a ser insertado en el trie
	 * @throws Exception Si el elemento que se desea agregar no es correcto
	 * @return true si agregado , false de lo contrario
	 */
	public boolean agregar( String nPalabra, T nElemento ) throws Exception
	{
		boolean agregado = false;
		if(nPalabra.length() == 0)
		{
			throw new Exception ("el elemento que se desea agregar no es correcto");
		}
		else
		{
			if (raiz.agregar(nElemento, nPalabra))
			{
				peso ++;
				agregado = true;
			}
		}
		return agregado;
	}

	/**
	 * Busca el elemento del trie cuya representacion en String corresponte a la palabra que llega por parametro. <br>
	 * <b> pre: </b> nPalabra!=null. <br>
	 * <b> post: </b> Se retorna el elemento del trie cuya representacion en String corresponde a la palabra dada. null de lo contrario
	 * @param nPalabra Palabra a ser buscada
	 * @return Los elementos del trie cuya cuya representacion en String corresponte a la palabra que llega por parametro. null si no existe tal elemento
	 */
	public Iterator<T> buscar( String nPalabra )
	{
		return raiz.buscar( nPalabra );
	}

	/**
	 * Busca todos los elementos asociados con el prefijo dado.<br>
	 * <b> pre: </b> prefijo!=null. <br>
	 * <b> post: </b> Se retorno la lista de elementos que contienen el prefijo dado.
	 * @param prefijo El prefijo del que se desean los elementos asociados
	 * @return La lista de elementos correspondiente al prefijo dado
	 */
	public Iterator<T> buscarPorPrefijo( String prefijo )
	{
		IteradorSimple<T> respuesta = new IteradorSimple <T>( peso );
		raiz.buscarPorPrefijo(prefijo, respuesta);
		return respuesta;
	}

	/**
	 * Retorna el peso del trie <br>
	 * <b>post: </b> Se retorno el peso del trie
	 * @return El peso del trie
	 */
	public int darPeso( )
	{
		peso = raiz.darPeso( );
		return peso;
	}
	
	/**
	 * Elimina los elementos
	 * @param nombre nobmre de los elementos que toca eliminar
	 * @return Iterador con lo elementos eliminados.
	 */
	public Iterator< T > eleminar ( String nombre )
	{
		IteradorSimple< T > iterElementos = new IteradorSimple<T>( darPeso( ) );
		raiz.eliminar(nombre, iterElementos);
		return iterElementos;
	}

	/**
	 * Elimina los elementos con un sufijo
	 * @param sufijo Sufijo de los elementos a eliminar
	 * @return  Iterador con lo elementos eliminados.
	 */
	public Iterator< T > emliminarPorPrefijo ( String sufijo )
	{
		IteradorSimple< T > iterElementos = new IteradorSimple< T >( darPeso( ) );
		raiz.eliminarElementosPorPrefijo( sufijo, iterElementos );
		return iterElementos;
	}
	
	/**
	 * Recorrido en pos orden.
	 * @return Retorna un iterador con lo elementos ordanizados en pos orden.
	 */
	public Iterator < T > recorridoPosOrden ( )
	{
		IteradorSimple< T > iter = new IteradorSimple< T >( darPeso( ) );
		raiz.recorridoPosOrden( iter );
		return iter;
	}
	
	/**
	 * Recorrido en pre orden.
	 * @return Retorna un iterador con lo elementos ordanizados en pre orden.
	 */
	public Iterator < T > recorridoPreOrden ( )
	{
		IteradorSimple< T > iter = new IteradorSimple< T >( darPeso( ) );
		raiz.recorridoPreOrden( iter );
		return iter;
	}
	
	/**
	 * Recorrido en por nievles.
	 * @return Retorna un iterador con lo elementos ordanizados en pos orden.
	 */
	public Iterator < T > recorridoPorNiveles ( )
	{
		IteradorSimple< T > iter = new IteradorSimple< T >( darPeso( ) );
		raiz.recorridoPorNiveles( iter );
		return iter;
	}

}
